package Vertex;

import java.util.LinkedList;

public class orangesRotting {
    public int orangesRotting(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return -1;
        }

        int rows = grid.length;
        int cols = grid[0].length;
        LinkedList<int[]> queue = new LinkedList<>();
        int freshCount = 0;

        // 初始化队列和新鲜橘子的数量
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 2) {
                    queue.offer(new int[]{r, c});
                } else if (grid[r][c] == 1) {
                    freshCount++;
                }
            }
        }

        int minutes = 0;
        while (!queue.isEmpty() && freshCount > 0) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] pos = queue.poll();
                int r = pos[0];
                int c = pos[1];
                for (int[] direction : new int[][]{{0,1}, {1,0}, {0,-1}, {-1,0}}) {
                    int newR = r + direction[0];
                    int newC = c + direction[1];
                    if (newR >= 0 && newR < rows && newC >= 0 && newC < cols && grid[newR][newC] == 1) {
                        grid[newR][newC] = 2;
                        freshCount--;
                        queue.offer(new int[]{newR, newC});
                    }
                }
            }
            minutes++;
        }

        return freshCount > 0 ? -1 : minutes;
    }
}
